/**
 * 105. 从前序与中序遍历序列构造二叉树
 * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
 */
const { TreeNode } = require('../../libs/public');

/**
 * @param {number[]} preorder
 * @param {number} beginPre
 * @param {number} endPre
 * @param {number[]} inorder
 * @param {number} beginIn
 * @param {number} endIn
 * @return {TreeNode}
 */
function recursion(preorder, beginPre, endPre, inorder, beginIn, endIn) {
  if (beginPre > endPre) {
    return null;
  }
  if (beginPre === endPre) {
    return new TreeNode(preorder[beginPre], null, null);
  }
  const val = preorder[beginPre];
  const rootIndexIn = inorder.indexOf(val, beginIn);
  const leftCount = rootIndexIn - beginIn;
  return new TreeNode(
    val,
    recursion(preorder, beginPre + 1, beginPre + leftCount, inorder, beginIn, rootIndexIn - 1),
    recursion(preorder, beginPre + leftCount + 1, endPre, inorder, rootIndexIn + 1, endIn),
  );
}

/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
function buildTree(preorder, inorder) {
  const last = preorder.length - 1;
  return recursion(preorder, 0, last, inorder, 0, last);
}

console.log(JSON.stringify(buildTree([3, 9, 20, 15, 7], [9, 3, 15, 20, 7]), null, 2));
console.log(JSON.stringify(buildTree([-1], [-1]), null, 2));
